/*
 * @lc app=leetcode.cn id=735 lang=golang
 *
 * [735] 小行星碰撞
 */
package Solutions

// @lc code=start

func asteroidCollision(asteroids []int) []int { //[1,1,-1,-2]
	R := len(asteroids) + 1
	L := -2
	bomMax := make([]int, len(asteroids))
	for i := 0; i < len(bomMax); i++ {
		bomMax[i] = -1
	}
	var d func(i int) int
	d = func(i int) int {
		if bomMax[i] != -1 {
			return bomMax[i]
		}
		for j := i + 1; j < len(asteroids); j++ {
			if asteroids[j] > 0 {
				t := d(j)
				if t == R {
					bomMax[i] = t
					return t
				}
				if asteroids[j] == -asteroids[t] {
					j = t
					continue
				}
				if asteroids[i] < -asteroids[t] {
					bomMax[i] = t
					return t
				} else if asteroids[i] <= -asteroids[t] {
					bomMax[i] = t
					bomMax[t] = L
					return t
				} else {
					bomMax[t] = L
				}
			} else {
				if asteroids[i] < -asteroids[j] {
					bomMax[i] = j
					return j
				} else if asteroids[i] == -asteroids[j] {
					bomMax[i] = j
					bomMax[j] = L
					return j
				} else {
					bomMax[j] = L
				}
			}

		}
		bomMax[i] = R
		return R
	}
	ans := make([]int, 0, len(asteroids))
	for i := 0; i < len(asteroids); i++ {
		if asteroids[i] < 0 {
			if bomMax[i] != L {
				ans = append(ans, asteroids[i])
			}
		} else {
			p := d(i)
			if p == R {
				ans = append(ans, asteroids[i])
			}
		}
	}
	return ans
}
func absInt(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

// @lc code=end
